package algorithm.dynamic_programming;

import java.util.HashMap;

public class StickersToSpellWord {


    public static int minStickers(String[] stackers, String target){
        if(stackers == null || stackers.length ==0)
            return -1;
        int n = stackers.length;
        int[][] map = new int[n][26];
        for (int i = 0; i < n; i++) {
            char[] chars = stackers[i].toCharArray();
            for (int j = 0; j < chars.length; j++) {
                map[i][chars[j] - 'a']++;
            }
        }
        HashMap<String, Integer> dp = new HashMap<>();
        dp.put("", 0);
        return process(map, target, dp);
    }

    public static int process(int[][] map, String rest, HashMap<String, Integer> dp){
        if(dp.containsKey(rest))
            return dp.get(rest);

        char[] chars = rest.toCharArray();
        int[] tmap = new int[26];
        for (int i = 0; i < chars.length; i++) {
            tmap[chars[i] - 'a']++;
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < map.length; i++) {
            if (map[i][chars[0] - 'a'] == 0)
                continue;

            StringBuffer buffer = new StringBuffer();
            for (int j = 0; j < 26; j++) {
                if(tmap[j] != 0){
                    int temp = Math.max(0, tmap[j] - map[i][j]);
                    while(temp > 0){
                        buffer.append((char) ('a' + j));
                        temp--;
                    }
                }
            }
            int process = process(map, buffer.toString(), dp);
            if(process != -1){
                result = Math.min(result, process);
            }
        }
        dp.put(rest, result == Integer.MAX_VALUE ? -1 : result + 1);
        return dp.get(rest);
    }

    public static void main(String[] args) {
        String[] arr = {"aaaa","bbaa","ccddd"};
        String str = "abcccccdddddbbbaaaaa";
        System.out.println(minStickers(arr, str));
    }

}
